package com.etc.homework;

import java.util.Arrays;
import java.util.Random;

/**
 * @author: knowno
 * @create: 2024-09-04 14:05
 * @Version 1.0
 * 快速排序是一种比较高效的排序算法，采用“分而治之”的思想，通过多次比较和交换来实现排序，在一趟排序中把将要排序的数据分成两个独立的部分，对这两部分进行排序使得其中一部分所有数据比另一部分都要小，然后继续递归排序这两部分，最终实现所有数据有序。
 **/
public class QuickSort {

    /**
     * 选定一个基准位置的值[左侧第一个],比基准位置的值大的元素放在右侧，比基准位置的值小的放在左侧
     * * 定义两个指针: 移动 left ++   right --    left<right
     * * 退出条件 left > right
     * * 右侧遍历，right --操作,如果发现了比基准位置的值小的暂停移动
     * * 左侧遍历，left ++操作，如果发现了比基准位置大的，暂停移动
     * * 交换左右两个指针对应元素
     * * 当指针相遇的时候  left == right 当前值和基准值交换位置
     */
    public static void quickSorting(Student arr[], int low, int high) {

        //当low>=high,方法终止
        if (low >= high) {
            return;
        }
        //设置基准位,最左侧的元素
        Student pivot = arr[low];
//        System.out.println("当前pivot: " + pivot);
        //左侧向右移动的"指针"=>变量
        int left = low;
        //右侧向左移动的 变量
        int right = high;
        //循环来处理指针的移动(left ++ , right --),条件 未相遇
        while (left < right) {

            //右侧开始
            while (left < right && arr[right].getAge() >= pivot.getAge()) {
                //只需要向左移动即可.
                right--;
            }
            //左侧向右
            while (left < right && arr[left].getAge() <= pivot.getAge()) {
                left++;
            }

            //交换
            if (left < right) {
                //arr[left] arr[right]
                Student t = arr[left];
                arr[left] = arr[right];
                arr[right] = t;
            }
        }
        //相遇， 当前值和基准值交换位置
        arr[low] = arr[left];
        arr[left] = pivot;
//        System.out.println("当前数组: " + Arrays.toString(arr));
        //递归来调用函数，分别实现左侧排序
        if (low < left) {
            quickSorting(arr, low, left - 1);
        }
        //递归来调用函数，分别实现右侧排序
        if (right < high) {
            quickSorting(arr, right + 1, high);
        }
    }

}
